\documentclass[a4paper]{article}
\usepackage{xeCJK}
%\setlength\textwidth{180pt}
\usepackage{indentfirst}
\usepackage{pdfpages} 
\usepackage{listings}
\usepackage{color}
\usepackage[svgnames]{xcolor}
\usepackage{tikz}
\usepackage{fancybox}
\usetikzlibrary{decorations.pathmorphing} % noisy shapes
\usetikzlibrary{fit}					% fitting shapes to coordinates

\usepackage[left=1.8cm,right=1.8cm,top=2cm,bottom=1.5cm]{geometry}
\setmainfont{WenQuanYi Micro Hei}
\setCJKmonofont{WenQuanYi Micro Hei}
%\lstset{ language=C, numbers=left, basicstyle=\small\ttfamily\bfseries,
 % keywordstyle=\color{blue}, commentstyle=\color{comment},
  %stringstyle=\color{red}, frame=shadowbox, breaklines=true,
  %backgroundcolor=\color{lightgray},escapeinside=`` }
\lstset{                        %Settings for listings package.
  language=[ANSI]{C},
  backgroundcolor=\color{lightgray},
  basicstyle=\footnotesize,
  breakatwhitespace=false,
  breaklines=true,
  captionpos=b,
  commentstyle=\color{olive},
  directivestyle=\color{blue},
  extendedchars=false,
  frame=single,
  framerule=0.3pt,
  keywordstyle=\color{blue}\bfseries,
  morekeywords={*,define,*,include...},
  numbersep=5pt,
  %numbers=left,
  rulesepcolor=\color{red!20!green!20!blue!20},
  showspaces=false,
  showstringspaces=false,
  showtabs=false,
  stepnumber=2,
  stringstyle=\color{purple},
  tabsize=4,
  title=\lstname
}
\definecolor{lightgray}{RGB}{230,230,230}
\definecolor{comment}{RGB}{0,180,100}
\newcommand{\clbox}[1]{\fcolorbox{black}{Lavender}{\vbox{#1}}}
\newcommand{\qebox}[1]{\fcolorbox{black}{pink}{\vbox{#1}}}
\newcommand{\imwords}[1]{\textbf{\color{red}#1}}
% 非常重要, listings关闭非ASCII字符兼容
\lstset{extendedchars=false}
\title{JOS Lab2}
\author{00848161	谢睿明}
\date{}
\begin{document}
\maketitle

\section{Exercise 1}
\noindent
\clbox{In the file kern/pmap.c, you must implement code for the following functions.

    boot\_alloc()

	page\_init()

	page\_alloc()

	page\_free()
	
You also need to add some code to i386\_vm\_init() in pmap.c, as indicated by comments there. For now, just add the code needed leading up to the call to check\_page\_alloc().

You probably want to work on boot\_alloc(), then i386\_vm\_init(), then page\_init(), page\_alloc(), and page\_free().

check\_page\_alloc() tests your physical page allocator. You should boot JOS and see whether check\_page\_alloc() reports success. Fix your code so that it passes. You may find it helpful to add your own assert()s to verify that your assumptions are correct. }
\newline
\par{第一个Exercise是要写一个物理页面分配的算法，这个分配器维护一个空闲页的队列，记录哪些页面是空闲的。在开始Coding之前，首先需要对Lab2新加入的内容有一些了解，看看Lab2究竟比Lab1多出了什么东西。}
\par{分析inic.c文件，发现Lab2在进入monitor之前又调用了两个函数，分别是：i386\_detect\_memory()和i386\_vm\_init()，这两个函数在pmap.c文件中定义。第一个函数并不需要我们填写，主要功能就是计算当前的物理内存大小和最大物理地址。我们主要关注的是第二个函数，从注释可以看到，这个函数的功能是建立起一个二级页表，并实现页式寻址。}
\par{Lab2还定义了很多宏，用于处理页面队列和虚实地址转换等等，另外还定义了一堆变量。在Exercise1中最好对页面队列的宏还有对应的变量有一些了解，下面简单介绍几个：首先是pmap.c中的page\_free\_list，它是Page\_list类型的，这个类型在memlayout.h中用LIST\_HEAD这个宏定义了。实际上Page\_list类型就是一个结构体里面包着一个Page*型的指针，变量名叫做lh\_first。而Page类型是一个结构体，包含一个指向之后节点的指针，和一个指向之前节点的指针的指针，和一个引用次数。}
\par{下面还有一些宏和变量（比如LIST\_FIRST），在用到的时候将会解释。}
\par{现在开始填写Exercise1，首先是boot\_alloc函数，这个函数的两个参数n和align分别为要分配空间的大小和对齐的参数。分配n字节的align对齐的物理内存。然后返回新分配空间的指针。实现这个函数需要注意的是对齐和虚实地址的转换。下面是函数实现：}
\begin{lstlisting}
  static void*
  boot_alloc(uint32_t n, uint32_t align)
  {
    extern char end[];
    void *v;
    if (boot_freemem == 0)
    boot_freemem = end;

    boot_freemem = ROUNDUP(boot_freemem, align);//align on 'align'
    v = boot_freemem;
    boot_freemem += n;
    assert(PADDR(boot_freemem) <= maxpa);// panic if the memory exceeded,cuz boot_freemem is kernel addr,should be transformed to phy addr
    return v;
  }
\end{lstlisting}
\par{下面是page\_init函数，这个函数标志当前物理页的使用情况，用来建立新的空闲页队列。}
\par{这个函数需要用到几个宏，在这里进行简要的介绍：
\begin{itemize}
\item LIST\_INIT宏：这个宏用于初始化空闲页队列，将表头设置为空。
\item LIST\_INSERT\_HEAD宏：这个宏将一个页插入到表头。
\item ROUNDUP宏：这个宏接受输入n和m，将n向上取整为m的倍数。
\end{itemize}}
\par{按照注释的提示，可以看出第1页（序号为0），[IOPHYSMEM, EXTPHYSMEM)，[EXTPHYSMEM, boot\_freemem)，处于这几段中的页是非空闲的。其余的页都是空闲的，可以将其加入空闲页队列中去。在这里需要注意的是，由于物理地址是连续的，但是页面是间断的。只有页面对应的4k物理地址全部为空闲，这个页面才是空闲的。所以对于非空闲但是又没有填满一页的空间来说，所在的这一页是不空闲的。这可以通过向上取整来实现。}
\begin{lstlisting}
  void
  page_init(void)
  {
    int i;
    LIST_INIT(&page_free_list); //init the free page list
    int base_page = (basemem + PGSIZE - 1) / PGSIZE; //ROUNDUP
    pages[0].pp_ref = 1;
    for (i = 1; i < base_page; i++) {
      pages[i].pp_ref = 0;
      LIST_INSERT_HEAD(&page_free_list, &pages[i], pp_link); //from page1 2 basemem
    }
    int io_page = (EXTPHYSMEM + PGSIZE - 1) / PGSIZE;
    for(i = base_page; i < io_page; i ++) //IOMEM should be not free
    {
      pages[i].pp_ref = 1;
    }
    int v =  ROUNDUP(PADDR(boot_freemem), PGSIZE) / PGSIZE; //must change 2 phy addr and then roundup
    for(i = v ; i < npage; i++)
    {
      pages[i].pp_ref = 0;
      LIST_INSERT_HEAD(&page_free_list, &pages[i], pp_link);
    }
    
  }
\end{lstlisting}
\par{需要注意的是，boot\_freemem为内核地址，需要转换成物理地址使用。npage代表的是总页数，也就是最大物理地址除去页面的大小。看注释的时候我有一个疑问，就是basemem和IOPHYSMEM之间的空间怎么办，但是查找之后发现这两者是一样的，中间没空间。}
\par{page\_alloc函数从空闲页队列头中取出一页分配，在这里需要运用到一个新的宏:LIST\_REMOVE，这个宏去除队列中的指定元素。在page\_alloc中，首先使用LIST\_FIRST得到队列首元素，然后将其从空闲队列中删去，对其进行初始化，最后返回这个新的页。}
\begin{lstlisting}
  int
  page_alloc(struct Page **pp_store)
  {
    // Fill this function in
    if(LIST_EMPTY(&page_free_list)) //no free pages
    return -E_NO_MEM;    
    *pp_store = LIST_FIRST(&page_free_list); //get first page
    LIST_REMOVE(*pp_store, pp_link);//remove
    page_initpp(*pp_store);//init the page
    return 0;
  }
\end{lstlisting}
\par{page\_free是最简单的函数，它只需要做两件事，1，检查这个页的ref值是否为0，不为0什么也不做。2，如果为0，那么就将这个页插入到空闲页队列的头部。}
\par{最后是修改i386\_vm\_init函数，这个函数要我们做的事情就是将Page数组存入内核中，这样内核就可以追踪到每一个页的状态。}
\section{Exercise 2}
\noindent
\clbox{Read chapters 5 and 6 of the Intel 80386 Reference Manual, if you haven't done so already. You can skip 6.3. Although JOS relies most heavily on page translation, you will also need a basic understanding of how segmentation works in protected mode to understand what's going on in JOS. }
\par{\imwords{Done.}}
\section{Exercise 3}
\noindent
\clbox{While GDB can only access QEMU's memory by virtual address, it's often useful to be able to inspect physical memory while setting up virtual memory. Review the QEMU monitor commands, especially the xp command, which lets you inspect physical memory. To access the QEMU monitor, press Ctrl-a c in the terminal (the same binding returns to the serial console).

Use the xp command in the QEMU monitor and the x command in GDB to inspect memory at corresponding physical and virtual addresses and make sure you see the same data.

QEMU's info mem command may also prove useful in the lab. We've also added an info pg command to our patched version of QEMU that prints out the current page table. }
\par{\imwords{Done.}}
\newline
\newline
\qebox{
Question1: Assuming that the following JOS kernel code is correct, what type should variable x have, uintptr\_t or physaddr\_t?

      	mystery\_t x;
      	char* value = return\_a\_pointer();
      	*value = 10;
      	x = (mystery\_t) value;}
\par{x的类型是uintptr\_t，因为这里没有明显的进行物理地址的转换，程序中使用的地址均为虚拟地址。}
\section{Exercise 4}
\noindent
\clbox{In the file kern/pmap.c, you must implement code for the following functions.

        pgdir\_walk()

        boot\_map\_segment()

        page\_lookup()

        page\_remove()

        page\_insert()
	

page\_check(), called from i386\_vm\_init(), tests your page table management routines. You should make sure it reports success before proceeding. }
\par{Exercise 4开始涉及到页的具体操作，比如查找，增加，删除等等。需要注意的是最好按照顺序完成这些函数，因为后边的函数需要用到前边已经实现的函数来实现。}
\par{pgdir\_walk函数，输入pgdir,va,create三个量，第一个是指向页目录地址的指针，第二个是一个虚拟地址，第三个是用来决定是否要新建一个页表。JOS采用二级寻址，首先在页目录寻找页表地址，然后在页表中根据页表项找到特定的某一页，最后根据页内偏移得到具体地址。这个函数完成的功能是：将虚拟地址对应的页表项的指针返回。需要注意的一点是，页目录和页表项存储的都是物理地址，但是返回的指向页表项的指针必须是虚拟地址，在这里需要做一个转换。最后需要注意的就是权限问题，注释上说mmu单位会进行权限处理，所以不需设置的太严格，将PTE\_W,PTE\_P,PTE\_U三位设置一下即可，表示可写，存在，用户可见。}
\begin{lstlisting}
  pte_t *
  pgdir_walk(pde_t *pgdir, const void *va, int create)
  {
    // Fill this function in
    pde_t * entry = &pgdir[PDX(va)]; //virtual addr
    struct Page * newpage;
    if(*entry & PTE_P) //if the page table exists
    {
      entry = (pte_t*)KADDR(PTE_ADDR(*entry));//MUST change phyaddr 2 kernaddr!!!
      return &entry[PTX(va)];
    }    
    else
    {
      if(create == 0)
      return NULL;
      if(page_alloc(&newpage) != 0) //no free space
      return NULL;
      newpage -> pp_ref = 1;
      memset(KADDR(page2pa(newpage)), 0, PGSIZE);
      *entry = page2pa(newpage) | PTE_U | PTE_W | PTE_P;//permision
      // entry
      entry = (pte_t*)KADDR(PTE_ADDR(*entry));
      return &entry[PTX(va)];
    }    
  }
\end{lstlisting}
\par{boot\_map\_segment()，这个函数的作用是将一段虚拟地址映射到一段物理地址上。需要使用pgdir\_walk来完成，思路就是首先根据虚拟地址获得页表项的地址，然后映射一页的内容，接着继续一页一页的映射。关于标志位好像有一些问题，注释上说需要将PTE\_P位也置为1，可是在之后内核栈的检查中过不了，所以在这里只好不设置PTE\_P位。}
\begin{lstlisting}
  static void
  boot_map_segment(pde_t *pgdir, uintptr_t la, size_t size, physaddr_t pa, int perm)
  {
    // Fill this function in
    int i;
    pte_t * addr;
    for(i = 0;i < size; i += PGSIZE)
    {
      addr = pgdir_walk(pgdir, (void*)(la + i), 1);//get pte etry
      *addr = (pa + i) | perm ;//map page by page
    }
    return;
  }
\end{lstlisting}
\par{page\_lookup()，这个函数的作用是给定一个虚拟地址，返回这个虚拟地址所对应的页，以及对应页表项的地址。这个函数的思路也是使用pgdir\_walk，首先获得虚拟地址对应的页表项，获得页的物理地址，接着使用pa2page这个函数将其转换成页返回。}
\begin{lstlisting}
  struct Page *
  page_lookup(pde_t *pgdir, void *va, pte_t **pte_store)
  {
    // Fill this function in
    pte_t *entry = pgdir_walk(pgdir, (void *)va, 1);//get pte entry
    if(entry == NULL)
    return NULL;
    if(pte_store != 0)
    *pte_store = entry;
    return pa2page(*entry); //return the page
  }
\end{lstlisting}
\par{page\_remove()，这个函数输入一个虚拟地址，解除在这个虚拟地址上的物理页的映射关系。函数思路使用page\_lookup，如果这个地址上没有映射物理页面，则什么也不做。如果映射了，调用page\_decref函数解除映射，并且对应的页表项也要清0。如果删除了一个页表项，则对应的TLB项也需要清除。}
\begin{lstlisting}
  void
page_remove(pde_t *pgdir, void *va)
{
  pte_t * store = NULL;
  struct Page* page = page_lookup(pgdir, va, &store);
  if(page == NULL)//no page mapped here
    return;
  page_decref(page);
  if(store != NULL)
  {
      *store = 0; // make the entry zero
      tlb_invalidate(pgdir, va);//clean tlb
  }  
  return;
}
\end{lstlisting}
\par{page\_insert()，这个函数将一个物理页面映射到一段虚拟地址空间中，并设定权限。实现需要用到pgdir\_walk， page\_remove和page2pa三个函数，思路如下：首先使用pgdir\_walk得到页表项地址，按照要求create位应为1，并增加ref的值。如果这个页表项对应的页已经有物理地址映射，则需要用page\_remove解除映射，最后将物理页面映射到这个页上。}
\begin{lstlisting}
  int
  page_insert(pde_t *pgdir, struct Page *pp, void *va, int perm) 
  {
    pte_t * entry = pgdir_walk(pgdir, va, 1);
    if(entry == NULL)
      return -E_NO_MEM;
    pp -> pp_ref ++;
    if(*entry & PTE_P) //exists
      page_remove(pgdir, va);
    *entry = page2pa(pp) | perm | PTE_P;
    return 0;
  }
\end{lstlisting}
\section{Exercise 5}
\noindent
\clbox{Fill in the missing code in i386\_vm\_init() after the call to page\_check().

Your code should now pass the check\_boot\_pgdir() check. }
\par{这里需要将物理地址映射到三段的内核地址上。不是很难，有两个地方需要注意：1，在映射内核栈的时候，有一页是"保卫页"，这一页不能设定PTE\_P位。2，在将所有物理内存映射到KERNBASE时，大小为~KERNBASE + 1，也就是-KERNBASE，因为没法表示$2^{32}$。所以只能这么做。}
\newline
\qebox{Question2:What entries (rows) in the page directory have been filled in at this point? What addresses do they map and where do they point? In other words, fill out this table as much as possible: }\newline
\begin{tabular}{|c|c|c|}
\hline
Entry & Base Virtual Address  & Points to (logically): \\
\hline
1023 & 0xffc00000 & Page table for top 4MB of phys memory\\
\hline
. & . & .\\
\hline
960 & 0xf0000000 & Page table for first 4MB phy memory and kernel code\\
\hline
959 & 0xefc00000 & Page Directory (kernel RW)\\
\hline
958 & 0xef800000 & Page table for kernel stack\\
\hline
957 & 0xef400000 & Page Directory (user kernel R)\\
\hline
956 & 0xef000000 & Page table for struct Page[] pages\\
\hline
. & . & .\\
\hline
2 & 0x00800000 & NULL\\
\hline
1 & 0x00400000 & NULL\\
\hline
0 & 0x00000000 & same as 960\\
\hline
\end{tabular}
\newline  
\newline
\qebox{Question3: After check\_boot\_pgdir(), i386\_vm\_init() maps the first four MB of virtual address space to the first four MB of physical memory, then deletes this mapping at the end of the function. Why is this mapping necessary? What would happen if it were omitted? Does this actually limit our kernel to be 4MB? What must be true if our kernel were larger than 4MB?}
\par{Answer:因为JOS首先开启页式映射，接着关闭段式映射（也就是将段偏移量设置为0），在页式映射被开启，而段式映射尚未被关闭的时候，两者均有效。这就导致原本为KERNBASE之上的地址在经过段映射后会减去KERNBASE值，即被映射回0~256MB这个空间中。将虚拟地址的前4MB复制到物理地址的前4MB中，保证了在段式映射尚未关闭的时候，运行前4MB的代码不会受到影响，而我们知道内核代码是存在前4MB中的，所以整个内核程序的执行都没有问题。在执行了必要的代码将段式映射关闭后，就可以重新将物理地址的前4MB置为0，因为此时虚拟地址经过段式映射映射到的地址还是自己。如果这句话省略了，那么内核的执行就会出现问题，不能按照指定的代码执行。如果内核大于4MB，则可以映射多个页表，即将KERNBASE + i的页映射到物理地址为i上。}\\
\qebox{Question4: (From Lecture 4) We have placed the kernel and user environment in the same address space. Why will user programs not be able to read or write the kernel's memory? What specific mechanisms protect the kernel memory?}
\par{Answer:因为用户可能会有误操作，如果开放所有的权限可能会由于用户的误操作或者有意识的操作导致系统的崩溃。每一个个页设定有PTE\_U位，如果为1表示用户可以访问，为0则无法访问。}\\
\qebox{Question5: What is the maximum amount of physical memory that this operating system can support? Why?}
\par{Answer:256MB，因为物理内存被映射到KERNBASE以上，而KERNBASE到0xffffffff之间为256MB，所以最多可以支持的物理内存为256MB。}\\
\qebox{Question6: How much space overhead is there for managing memory, if we actually had the maximum amount of physical memory? How is this overhead broken down?}
\par{Answer:第一页，保留页(实模式的IDT和BIOS)。IO hole[IOPHYSMEM, EXTPHYSMEM)，npage * sizeof(struct Page)的空间用于存放pages数组，一页用来存放页目录，1024页用来存放页表，还有因为内存页对齐而空闲的空间。}
\section{Challenges}
\subsection{命令行扩展1}
\qebox{Challenge! Extend the JOS kernel monitor with commands to:

    * Display in a useful and easy-to-read format all of the physical page mappings (or lack thereof) that apply to a particular range of virtual/linear addresses in the currently active address space. For example, you might enter 'showmappings 0x3000 0x5000' to display the physical page mappings and corresponding permission bits that apply to the pages at virtual addresses 0x3000, 0x4000, and 0x5000.

    * Explicitly set, clear, or change the permissions of any mapping in the current address space.

    * Dump the contents of a range of memory given either a virtual or physical address range. Be sure the dump code behaves correctly when the range extends across page boundaries!

    * Do anything else that you think might be useful later for debugging the kernel. (There's a good chance it will be!)

}
\par{需要实现三个函数，showmappings, dump, setpermission，功能分别是：1、显示虚拟地址对应物理页地址和权限位。2、显示一段虚拟地址或者物理地址的内容。3、改变一个页的权限。}
\par{首先是showmappings函数，函数格式如下：sm  add1 add2,输出的是add1和add2之间的页地址以及权限。思路如下：首先使用pgdir\_walk函数获得初始地址对应的的页地址以及权限信息，将其输出，接着获得下一个页的地址和权限信息，每一次将初始地址加上页大小，直到地址大于结尾的地址为止。}
\par{接着是dump函数，函数格式如下：dump -p|-v add，第一个参数决定地址为虚拟地址还是物理地址。如果是物理地址那么需要转换成虚拟地址，使用KADDR宏可以实现转化。接着使用page\_lookup函数查看这个地址是否映射了某个物理地址，如果没有被映射则输出错误，如果被映射了则直接解引用这个地址就可以得到内容。}
\par{最后是setpermission函数，函数格式如下：perm -s|-c x addr，-s表示设置权限，-c表示清除权限，x表示欲设置/取消的权限。首先使用pgdir\_walk获得这个地址对应的页表项的地址，接着根据参数就可以对其进行设置，如果是加上某个权限就用或运算，反之用与运算。}
\subsection{命令行扩展2}
\qebox{Challenge! Extend the JOS kernel monitor with commands to allocate and free pages explicitly, and display whether or not any given page of physical memory is currently allocated. For example:

	K> alloc\_page

		0x13000

	K> page\_status 0x13000

		allocated

	K> free\_page 0x13000

	K> page\_status 0x13000

		free

	

Think of other commands or extensions to these commands that may be useful for debugging, and add them. }
\par{这个Challenge也需要实现三个函数，pagealloc,pagestatus,pagefree。功能如题目所示。}
\par{pagealloc函数其实就是调用pmap.c中的page\_alloc函数，并使用page2pa函数来将返回的页转换成物理地址并输出。}
\par{pagestatus同理，将物理地址转化成页，然后查看pp\_ref值，如果大于0则说明不是空闲页，否则就是空闲页。}
\par{pagefree，也先将物理地址转化成页，接着将pp\_ref置为0，调用page\_free函数即可。}
\end{document}




